public class Levenshtein {

	/**
	 * Calculates the Levenshtein distance between two Candidates
	 * 
	 * @param candidate
	 * @param candidate2
	 * @return
	 */
	public static int calculateDistance(Candidate candidate,
			Candidate candidate2) {
		// the smaller one must be the first parameter, for efficiency
		if (candidate.getEvents().length > candidate2.getEvents().length) {
			return Levenshtein.calcLevenshteinDistance(candidate2.getEvents(),
					candidate.getEvents());
		}
		return Levenshtein.calcLevenshteinDistance(candidate.getEvents(),
				candidate2.getEvents());
	}

	/**
	 * Calculates the Levenshtein distance between two arrays of events. The
	 * first array's length MUST be smaller than the second's.
	 * 
	 * @param events
	 * @param events2
	 * @return
	 */
	private static int calcLevenshteinDistance(Event[] events, Event[] events2) {
		// degenerate cases
		if (events.equals(events2)) {
			return 0;
		}
		if (events.length == 0) {
			return events2.length;
		}
		if (events2.length == 0) {
			return events.length;
		}

		// create two work vectors of integer distances
		int[] v0 = new int[events2.length + 1];
		int[] v1 = new int[events2.length + 1];

		for (int i = 0; i < v0.length; i++) {
			v0[i] = i;
		}

		for (int i = 0; i < events.length; i++) {
			// calculate v1 (current row distances) from the previous row v0

			// first element of v1 is A[i+1][0]
			// edit distance is delete (i+1) chars from s to match empty t
			v1[0] = i + 1;

			// use formula to fill in the rest of the row
			for (int j = 0; j < events2.length; j++) {
				int cost = (events[i] == events2[i]) ? 0 : 1;
				v1[j + 1] = Math.min(v1[j] + 1,
						Math.min(v0[j + 1] + 1, v0[j] + cost));
			}

			// copy v1 (current row) to v0 (previous row) for next interation
			for (int j = 0; j < v0.length; j++)
				v0[j] = v1[j];
		}

		return v1[events2.length];
	}
}
